/**
 * 二叉树遍历
 */

// 二叉树定义
function TreeNode(val, left, right) {
    return {val, left, right}
}

// 前序遍历
function preorderTraverse(root) {
    var result = []
    function doTraverse(root) {
        if (root == undefined) {
            return
        }
        result.addLast(root.val)
        doTraverse(root.left)
        doTraverse(root.right)
    }
    doTraverse(root)
    return result
}

// 中序遍历
function inorderTraverse(root) {
    var result = []
    function doTraverse(root) {
        if (root == undefined) {
            return
        }
        doTraverse(root.left)
        result.addLast(root.val)
        doTraverse(root.right)
    }
    doTraverse(root)
    return result
}

// 后序遍历
function postorderTraverse(root) {
    var result = []
    function doTraverse(root) {
        if (root == undefined) {
            return
        }
        doTraverse(root.left)
        doTraverse(root.right)
        result.addLast(root.val)
    }
    doTraverse(root)
    return result
}

// 层序遍历
function levelTraverse(root) {
    var result = []
    var queue = [root]
    while (!queue.isEmpty()) {
        var cnt = queue.length()
        for (var i = 0; i < cnt; ++i) {
            var n = queue.removeFirst()
            result.addLast(n.val)
            if (n.left != undefined) {
                queue.addLast(n.left)
            }
            if (n.right != undefined) {
                queue.addLast(n.right)
            }
        }
    }
    return result
}

var root = TreeNode(1, TreeNode(2, TreeNode(4, TreeNode(7), undefined), TreeNode(5)), TreeNode(3, undefined, TreeNode(6)))

println(preorderTraverse(root))
println(inorderTraverse(root))
println(postorderTraverse(root))
println(levelTraverse(root))
